import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/7 20:16
 * @description 思路：排序 + 前缀和 + 二分查找 + Map
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {60864,25176,27249,21296,20204};
        solution.findBestValue(arr, 56803);
    }

    public int findBestValue(int[] arr, int target) {
        int sum = 0;
        for (int a : arr) {
            sum += a;
        }
        int n = arr.length;
        Arrays.sort(arr);
        if (sum <= target) {
            return arr[n - 1];
        }
        int l = 0, r = arr[n-1];
        while (l <= r) {
            int mid = (l + r) / 2;
            int targetSum = help(sum, arr, mid);
            if (targetSum == target) {
                return mid;
            }
            if (targetSum < target) {
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }
        // 开始比较
        int sum1 = help(sum, arr,l);
        int sum2 = help(sum,arr, l -1);

        if(Math.abs(sum2-target)<=Math.abs(sum1-target)){
            return l-1;
        }else{
            return l;
        }
    }
    public int help(int sum, int[] arr, int k) {
        for (int a: arr) {
            if (a > k) {
                sum -= a - k;
            }
        }
        return sum;
    }

}
